The present invention relates to a packet switching system and, more particularly, to a pipeline scheduling method and system for the packet switch of a packet switching system.
Some recent packet switching systems use an input buffer type switch having N inputs and N outputs (N is a natural number) and N virtual output queuing (VOQ) elements in each input section.
FIG. 8 shows a conventional, general input buffer type packet switch having N inputs and N outputs (N is a natural number). Referring to FIG. 8, a packet switch 40 includes a plurality of input ports for inputting data, a plurality of output ports for outputting data, a data switch element 54 for transferring data input from the input ports to the output ports by switching them, and a scheduler 50 for controlling the data switch element 54.
Each input port has virtual output queuing (VOQ) elements 52. As the switch element 54, a cross-bar switch may be used. The scheduler 50 has a distributed scheduling architecture and is comprised of distributed scheduling modules 51-i (i=1 to N) arranged for the respective input ports. The packet switch 40 performs transfer within the cross-bar switch by using fixed-size packets. With this operation, the operation time of the switch system is quantized. This quantization unit will be referred to as a time slot.
The scheduler 50 receives pieces of connection request information (REQ) from the respective input ports for the respective output ports in units of time slots, and determines connection permission information (GRANT) between the input ports and the output ports on the basis of the connection request information. The scheduler 50 generates connection information (MSEL) between the input ports and the output ports on the basis of the connection permission information, and notifies the switch element 54 of the generated information, thereby setting input/output connections in the switch element 54.
The scheduler 50 generates, on the basis of connection permission information, transfer permission information (DSTMSG) indicating a specific output port from which data transfer is permitted with respect to each input port, and notifies each input port of the transfer permission information. Each input port outputs data to the switching element in accordance with the transfer permission information, and the corresponding output port receives the data, thereby completing switching.
The purpose of the scheduler 50 is to generate N×N pieces of connection permission information from N×N pieces of connection request information. To generate connection permission information, each of distributed scheduling modules 51-1 to 51-N determines connection permission/inhibition for each input port with respect to the corresponding output port. An output port to which a given distributed scheduling module 51-n (n is a natural number; 1≦n≦N) has given connection permission is a port “reserved” by another distributed scheduling module from the viewpoint of a distributed scheduling module 51-m (m≠N); connection permission cannot be given to this port. When a given distributed scheduling module determines connection permission for a given output port, this operation will be expressed as “reserving an output port” hereinafter.
As a distributed scheduling algorithm for a packet switch, an RRGS (Round Robin Greedy Scheduling) algorithm is available, which is disclosed in A. Smiljanic et al., “RRGS-Round-Robin Greedy Scheduling for Electronic/Optical Terabit Switches”, Globecom 99, November 1999.
In a scheduler using the RRGS algorithm, distributed scheduling modules are connected in a ring form, and messages are exchanged between adjacent distributed scheduling modules. According to the RRGS algorithm, each distributed scheduling module reserves (connection permission determination) a target time slot, and passes the resultant information to the next distributed scheduling module. The RRGS algorithm uses a pipeline function to relax the required message transfer rate condition.
A reservation process for a given time slot is completed when one cycle of message transfer is done among the respective distributed scheduling modules. In addition, according to the RRGS algorithm, N distributed scheduling modules reserve time slots at least N slots ahead of the current slot. Furthermore, in the RRGS algorithm, reservation processes for N time slots are made to simultaneously proceed with a phase shift of one time slot.
This RRGS algorithm may be modified such that reservation processes for a plurality of time slots are started at once from different distributed scheduling modules and made to proceed so as to be terminated simultaneously. This algorithm will be referred as framed RRGS hereafter.
FIG. 9 shows the arrangement of a distributed scheduler using RRGS and framed RRGS. FIG. 9 shows an arrangement with port count N=4 as an example. Referring to FIG. 9, the scheduler is comprised of IMs (Input Modules) 10-1 to 10-4. Each module 10-i (i=1 to 4) receives a frame pulse (FP) 21 indicating the head of a frame. Each module 10-i operates in synchronism with the frame pulse 21.
For each module 10-i, a physical number 23-i for module identification is set. Connection request information 11-i is input from each input port to the corresponding module 10-i, and the module 10-i determines a reservation (connection permission) in accordance with the arbitration result on the connection request, and outputs a corresponding one of pieces of connection permission information 12-1 to 12-4.
According to RRGS and framed RRGS, contention of connection requests for an output port is avoided by exchanging “output port reservation information”, which is information obtained by degenerating input port information from connection permission information (information generated by referring to input port information), between adjacent distributed scheduling modules. For example, the module 10-3 receives output port reservation information 14-2 from the preceding module 10-2 as output port reservation information 13-3, and uses it for arbitration of connection requests. Upon determining connection permission information, the module 10-3 notifies the succeeding module 10-4 of output port reservation information 14-3.
FIG. 10 shows scheduling based on RRGS disclosed in the above reference in a case where an odd number of ports are used. FIG. 10 shows a case where port count N=5, and a reservation sequence from time slot (TS) 6.
Scheduling for TS6 is executed as follows. TS1 represents a scheduling start time slot; and TS5, an end time slot. Reserving operation is started from a distributed scheduling module IM1 and ended at a distributed scheduling module IM5. First of all, in TS1, the distributed scheduling module IM1 performs reserving operation, and transfers output port reservation information for TS6 to a distributed scheduling module IM2.
In TS2, the distributed scheduling module IM2 performs reserving operation, and transfers output port reservation information for TS6 to a distributed scheduling module IM3. Subsequently, the distributed scheduling module IM3 performs reserving operation and information transfer in TS3, and a distributed scheduling module IM4 performs reserving operation and information transfer in TS4. When a distributed scheduling module IM5 performs reserving operation in TS5, reserving operation of the distributed scheduling modules for TS6 is completed, and the reservation result is used in TS6.
Scheduling for TS7 is performed by making the distributed scheduling modules IM5, IM1, IM2, IM3, and IM4 sequentially perform reserving operation and transfer output port reservation information in the interval between TS2 and TS6 in the order named. Subsequently, scheduling for TS8 and TS9 is executed in the same manner.
In this case, at the respective times, the respective distributed scheduling modules IM execute reserving operations for different times. For example, in TS5, the distributed scheduling module IM1 executes reserving operation for reservation time slot TS8; the distributed scheduling module IM2, for TS10; the distributed scheduling module IM3, for TS7; the distributed scheduling module IM4, for TS9; and the distributed scheduling module IM5, for TS6.
FIG. 11 shows scheduling based on RRGS disclosed in the above reference in a case where an even umber number of ports are used. FIG. 11 shows a case where port count N=4, and a reservation sequence from time slot (TS) 6.
This case differs from that in FIG. 10 in that when a reservation in a given time slot is executed, information transfer must be stopped in a time slot in the process of reserving operation. Referring to FIG. 11, the hatched portions represent such time slots in which information transfer must be stopped. As described above, according to RRGS, pipeline processing differs depending on whether the number of input ports is an even or odd number.
FIG. 12 shows a case where port count N=4, and a reservation sequence from TS5.
This scheduling operation differs from scheduling operations based on RRGS in FIGS. 10 and 11 in that the respective distributed scheduling modules IM1 to IM4 simultaneously start reserving operations for different time slots at a given timing, and also simultaneously terminate the reserving operations.
In the above distributed scheduling algorithm, each input module IM must perform reception of output port reservation information, expansion of the received information, reservation processing and updating of information by using the received information, format conversion of the updated information, and transmission of the information. According to the above conventional algorithm, the above processing is completed in one time slot (TS) in a time chart.
FIG. 13 shows the details of each time slot (TS) in FIGS. 10 to 12. Referring to FIG. 13, one time slot in FIGS. 10 to 12 is expressed as the interval between time T0 and time T4.
More specifically, each input module IM receives information from the adjacent input module IM in the interval between time T0 and time T1. Each module expands the information in the interval between time T1 and time T2. In this interval, the module converts the information into parallel information if the information was transferred serially. In the interval between time T2 and time T3, the module executes reservation processing. In the interval between time T3 and time T4, the module converts the information into a format for transfer. In this interval, for example, the module performs serial/parallel conversion or the like to serially transfer the information. In the interval between time T4 and time T5, the module transmits the information to the adjacent input module IM (the interval between T0 and T1 is equal to the interval between T4 and T5).
As described above, when reservation processing (T2 to T3) and other processing (to be referred to as transfer processing hereinafter) are to be executed within a single time slot, the times assigned to the respective processes are limited. This makes it difficult to flexibly cope with an increase in the number of ports by using the conventional algorithm. If, for example, the number of ports increases, the time required for a given input port to select one of output ports and perform reserving operation for the port is prolonged in reservation processing (T2 to T3). In addition, as the number of ports increases, the amount of output port reservation information to be transferred between the input modules IM increases.
Furthermore, when output port reservation information is to be serially transferred, the information transfer time (T0 to T1), information expansion time (T1 to T2), format conversion time (T3 to T4), and information transfer time (T4 to T5) are prolonged. Since the total time of these times and the above reservation processing time must be limited within one time slot, severe limitations are imposed on the number of ports.
When output port reservation information is to be transferred in parallel, the information expansion time (T1 to T2) and format conversion time (T3 to T4) can be omitted. In this case, however, the number of signal lines required for transfer between the IMs increases. When, therefore, IMs are to be implemented by a Large Scale Integration (LSI), the number of terminals of the LSI becomes too large to integrate the IMs into one LSI.